﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using DiscoveryLogic.Analytics.BusinessLogic.Measures;
using DiscoveryLogic.Analytics.DataObjects;
using DiscoveryLogic.Analytics.DataObjects.Networks;
using DiscoveryLogic.Common.Utilities;

namespace DiscoveryLogic.Analytics.BusinessLogic.Clusters
{
    public class NetworkDensityClusterWorker
    {
        private Network _Network;

        public NetworkDensityClusterWorker(Network network)
        {
            this._Network = network;
        }

        public void ClusterNetworkByDegreeDensity(int degreeThreshold)
        {
            Dictionary<EntityBase,int> vDegrees=new Dictionary<EntityBase, int>();
            Dictionary<EntityType,Dictionary<string,EntityBase>> entities=new Dictionary<EntityType, Dictionary<string, EntityBase>>();
            foreach(EntityBase entity in this._Network.Records)
            {
                if(entities.ContainsKey(entity.EntityType))
                {
                    Dictionary<string,EntityBase> entityBases= entities[entity.EntityType];
                    if(!entityBases.ContainsKey(entity.PKValue()))
                        entityBases.Add(entity.PKValue(), entity);
                    entities[entity.EntityType] = entityBases;
                }
                else
                {
                    Dictionary<string,EntityBase> entityBases=new Dictionary<string, EntityBase>();
                    entityBases.Add(entity.PKValue(), entity);
                    entities.Add(entity.EntityType, entityBases);
                }
            }
            Dictionary<EntityBase, List<EntityBase>> neighbors=new Dictionary<EntityBase, List<EntityBase>>();
            foreach(Link link in this._Network.Links)
            {
                EntityType fromType = EntityTypeUtil.GetEntityType(link.FromType);
                EntityBase fromEntity = entities[fromType][link.FromKey];
                EntityType toType = EntityTypeUtil.GetEntityType(link.ToType);
                EntityBase toEntity = entities[toType][link.ToKey];
                if (vDegrees.ContainsKey(fromEntity))
                    vDegrees[fromEntity] = vDegrees[fromEntity] + 1;
                else 
                    vDegrees.Add(fromEntity, 1);
                if (vDegrees.ContainsKey(toEntity))
                    vDegrees[toEntity] = vDegrees[toEntity] + 1;
                else 
                    vDegrees.Add(toEntity, 1);

                if(!neighbors.ContainsKey(fromEntity))
                {
                    List<EntityBase> adjacentEntities=new List<EntityBase>();
                    adjacentEntities.Add(toEntity);
                    neighbors.Add(fromEntity, adjacentEntities);
                }
                else
                {
                    List<EntityBase> adjacentEntities = neighbors[fromEntity];
                    if (!adjacentEntities.Contains(toEntity))
                        adjacentEntities.Add(toEntity);
                    neighbors[fromEntity] = adjacentEntities;
                }
                if (!neighbors.ContainsKey(toEntity))
                {
                    List<EntityBase> adjacentEntities = new List<EntityBase>();
                    adjacentEntities.Add(fromEntity);
                    neighbors.Add(toEntity, adjacentEntities);
                }
                else
                {
                    List<EntityBase> adjacentEntities = neighbors[toEntity];
                    if (!adjacentEntities.Contains(fromEntity))
                        adjacentEntities.Add(fromEntity);
                    neighbors[toEntity] = adjacentEntities;
                }
            }

            int seedID = 0;
            Dictionary<EntityBase, int> seeds=new Dictionary<EntityBase, int>();
            foreach(EntityBase entity in vDegrees.Keys)
            {
                if(seeds.ContainsKey(entity))
                    continue;

                if (vDegrees[entity] >= degreeThreshold)
                {
                    int existSeedID = 0;
                    List<EntityBase> neighborEntities = neighbors[entity];
                    foreach(EntityBase neighbor in neighborEntities)
                    {
                        if(seeds.ContainsKey(neighbor))
                        {
                            existSeedID = seeds[neighbor];
                            break;
                        }
                    }
                    if(existSeedID>0)
                    {
                        seeds.Add(entity, existSeedID);
                    }
                    else
                    {
                        seeds.Add(entity, ++seedID);
                    }
                }
                else
                {
                    seeds.Add(entity, ++seedID);
                }
            }

            Dictionary<int,List<EntityBase>> clusteredEntities=new Dictionary<int, List<EntityBase>>();
            foreach(EntityBase entity in seeds.Keys)
            {
                int sID = seeds[entity];
                if(clusteredEntities.ContainsKey(sID))
                {
                    List<EntityBase> groupedEntities = clusteredEntities[sID];
                    groupedEntities.Add(entity);
                    clusteredEntities[sID] = groupedEntities;
                }
                else
                {
                    List<EntityBase> groupedEntities=new List<EntityBase>();
                    groupedEntities.Add(entity);
                    clusteredEntities.Add(sID, groupedEntities);
                }
            }
            List<NetworkCluster> clusters=new List<NetworkCluster>();
            foreach(int clusterID in clusteredEntities.Keys)
            {
                NetworkCluster cluster=new NetworkCluster(clusterID,0,clusterID.ToString());
                clusters.Add(cluster);
            }
            
            NetworkCluster.Save(this._Network.NetworkName, clusters);
            // return this._Network;
        }


        #region min cut tree
        public void ClusterNetworkByMinCutTree(int clusterSizeThreshold)
        {
            Dictionary<int, NetworkCluster> clusters = new Dictionary<int, NetworkCluster>();
            Dictionary<int, List<EntityBase>> connectedEntities = this._Network.GroupConnectedEntities();
            List<EntityBase> orphanedEntities = new List<EntityBase>();
            foreach(int groupID in connectedEntities.Keys)
            {
                List<EntityBase> entities = connectedEntities[groupID];
                
                if (entities.Count > clusterSizeThreshold)
                {
                    this.FindCuts(entities, 0, clusterSizeThreshold, ref clusters);
                }
                else
                {
                    orphanedEntities.AddRange(entities);
                }
            }

            if (orphanedEntities.Count > 0)
            {
                int clusterID = clusters.Count + 1;
                NetworkCluster cluster = this.InitCluster(clusterID, 0, clusterSizeThreshold, orphanedEntities);
                clusters.Add(cluster.ClusterID, cluster);
            }

            Dictionary<int,List<int>> clusterChildClusters=new Dictionary<int, List<int>>();
            foreach(NetworkCluster cluster in clusters.Values)
            {
                if(clusterChildClusters.ContainsKey(cluster.ParentClusterID))
                {
                    List<int> childClusterIDs = clusterChildClusters[cluster.ParentClusterID];
                    if(!childClusterIDs.Contains(cluster.ClusterID))
                        childClusterIDs.Add(cluster.ClusterID);
                    clusterChildClusters[cluster.ParentClusterID] = childClusterIDs;
                }
                else
                {
                    List<int> childClusterIDs=new List<int>();
                    childClusterIDs.Add(cluster.ClusterID);
                    clusterChildClusters.Add(cluster.ParentClusterID, childClusterIDs);
                }
            }
            foreach(int clusterID in clusters.Keys)
            {
                NetworkCluster cluster = clusters[clusterID];
                if(clusterChildClusters.ContainsKey(clusterID))
                {
                    List<NetworkCluster> childClusters=new List<NetworkCluster>();
                    List<int> childClusterIDs = clusterChildClusters[clusterID];
                    foreach(int childClusterID in childClusterIDs)
                    {
                        childClusters.Add(clusters[childClusterID]);
                    }
                    cluster.ChildClusters = childClusters;
                }
            }
            List<NetworkCluster> clusterList = clusters.Values.ToList();
            NetworkCluster.Save(this._Network.NetworkName, clusterList);
            //return this._Network;
        }

        private void FindCuts(List<EntityBase> entities, int parentClusterID,
            int clusterSizeThreshold,
            ref Dictionary<int, NetworkCluster> clusters)
        {
            List<EntityBase> outputGroup1 = new List<EntityBase>();
            List<EntityBase> outputGroup2 = new List<EntityBase>();
            double densityAvg = 0;
            List<Link> includedLinks = Network.GetLinksConnectedToEntities(this._Network.Links, entities);

            for (int splitCount1 = 1; splitCount1 < entities.Count - 1; splitCount1++)
            {
                List<EntityBase> group1 = new List<EntityBase>();
                List<int> selection1 = this.Pick(splitCount1, entities.Count);
                for (int i = 0; i < selection1.Count; i++)
                {
                    int idx = selection1[i];
                    group1.Add(entities[idx]);
                }
                List<EntityBase> group2 = new List<EntityBase>();
                for (int i = splitCount1; i < entities.Count; i++)
                {
                    if (!selection1.Contains(i))
                        group2.Add(entities[i]);
                }
                int iteration = 0;
                int maxIteration = 100;
                int nullImprovement = 0;
                int nullImprovementBreakAt = 25;
                double densityScore = this.GetGroupDensity(group1,includedLinks) * this.GetGroupDensity(group2,includedLinks);
                if(densityScore > densityAvg)
                {
                    densityAvg = densityScore;
                    outputGroup1 = group1;
                    outputGroup2 = group2;
                }
                
                while (iteration < maxIteration)
                {
                    int sampleSize = Math.Min(group1.Count, group2.Count);
                    sampleSize = Math.Min(Math.Max(group1.Count, group2.Count)/3, sampleSize);
                    sampleSize = Math.Min(1, sampleSize);
                    List<int> picks1 = this.Pick(sampleSize, group1.Count);
                    List<int> picks2 = this.Pick(sampleSize, group2.Count);
                    List<EntityBase> newGroup1 = new List<EntityBase>();
                    List<EntityBase> newGroup2 = new List<EntityBase>();
                    this.RecombineList(group1, picks1, group2, picks2, out newGroup1, out newGroup2);
                    densityScore = this.GetGroupDensity(newGroup1,includedLinks) * this.GetGroupDensity(newGroup2,includedLinks);
                    if (densityScore > densityAvg)
                    {
                        outputGroup1 = newGroup1;
                        outputGroup2 = newGroup2;
                        group1 = newGroup1;
                        group2 = newGroup2;
                        densityAvg = densityScore;
                        nullImprovement = 0;
                    }
                    else
                    {
                        nullImprovement++;
                        if (nullImprovement > nullImprovementBreakAt)
                            break;
                    }
                    iteration++;
                }
            }
            int clusterID1 = clusters.Count + 1;
            NetworkCluster cluster1 = this.InitCluster(
                clusterID1, parentClusterID, clusterSizeThreshold, outputGroup1);
            clusters.Add(cluster1.ClusterID, cluster1);
            if (outputGroup1.Count > clusterSizeThreshold)
            {
                this.FindCuts(outputGroup1, clusterID1, clusterSizeThreshold, ref clusters);
            }
            int clusterID2 = clusters.Count + 1;
            NetworkCluster cluster2 = this.InitCluster(
                clusterID2, parentClusterID, clusterSizeThreshold, outputGroup2);
            clusters.Add(cluster2.ClusterID, cluster2);
            if (outputGroup2.Count > clusterSizeThreshold)
            {
                this.FindCuts(outputGroup2, clusterID2, clusterSizeThreshold, ref clusters);
            }
        }

        private double GetGroupDensity(
            List<EntityBase> group, 
            List<Link> links)
        {
            int intraEdgeCount = 0;
            int interEdgeCount = 0;
            Dictionary<EntityType,Dictionary<string, EntityBase>> includedEntities=new Dictionary<EntityType, Dictionary<string, EntityBase>>();
            foreach(EntityBase entity in group)
            {
                if(includedEntities.ContainsKey(entity.EntityType))
                {
                    Dictionary<string, EntityBase> entitis1 = includedEntities[entity.EntityType];
                    entitis1.Add(entity.PKValue(), entity);
                    includedEntities[entity.EntityType] = entitis1;
                }
                else
                {
                    Dictionary<string,EntityBase> entities1=new Dictionary<string, EntityBase>();
                    entities1.Add(entity.PKValue(), entity);
                    includedEntities.Add(entity.EntityType, entities1);
                }
            }
            foreach (Link link in links)
            {
                bool containsFromEntity = false;
                bool containsToEntity = false;
                EntityType fromType = EntityTypeUtil.GetEntityType(link.FromType);
                EntityType toType = EntityTypeUtil.GetEntityType(link.ToType);
                if(includedEntities.ContainsKey(fromType) && 
                    includedEntities[fromType].ContainsKey(link.FromKey))
                {
                    containsFromEntity = true;
                }
                if(includedEntities.ContainsKey(toType) && 
                    includedEntities[toType].ContainsKey(link.ToKey))
                {
                    containsToEntity = true;
                }
                if (containsFromEntity && containsToEntity)
                    intraEdgeCount++;
                else if (containsFromEntity || containsToEntity)
                    interEdgeCount++;
            }
            double density = (double)(intraEdgeCount - interEdgeCount);
            return intraEdgeCount;
        }

        private List<int> Pick(int sampleSize,int totalCount)
        {
            Debug.Assert(totalCount >= sampleSize);
            List<int> sample=new List<int>();
            Random rand=new Random((int)DateTime.Now.Ticks);
            while (sample.Count < sampleSize)
            {
                int idx = rand.Next(totalCount);
                if (!sample.Contains(idx))
                    sample.Add(idx);
            }
            return sample;
        }

        private void RecombineList(List<EntityBase> group1, List<int> picks1, 
            List<EntityBase> group2, List<int> picks2,
            out List<EntityBase> newGroup1, out List<EntityBase> newGroup2)
        {
            newGroup1=new List<EntityBase>();
            newGroup2=new List<EntityBase>();
            for (int i = 0; i < group1.Count; i++)
            {
                newGroup1.Add(group1[i]);
            }
            for (int i = 0; i < group2.Count; i++)
            {
                newGroup2.Add(group2[i]);
            }
            for(int i=0;i<picks1.Count;i++)
            {
                int idx1 = picks1[i];
                int idx2 = picks2[i];
                EntityBase placeHolder = newGroup2[idx2];
                newGroup2[idx2] = newGroup1[idx1];
                newGroup1[idx1] = placeHolder;
            }
        }

        private List<Link> FindLinksBetweenGroup(List<EntityBase> group1, List<EntityBase> group2)
        {
            List<Link> linksToCut=new List<Link>();
            Dictionary<EntityType, Dictionary<string, EntityBase>> includedEntities1 =
                new Dictionary<EntityType, Dictionary<string, EntityBase>>();
            foreach (EntityBase entity in group1)
            {
                if (includedEntities1.ContainsKey(entity.EntityType))
                {
                    Dictionary<string, EntityBase> entitis1 = includedEntities1[entity.EntityType];
                    entitis1.Add(entity.PKValue(), entity);
                    includedEntities1[entity.EntityType] = entitis1;
                }
                else
                {
                    Dictionary<string, EntityBase> entities1 = new Dictionary<string, EntityBase>();
                    entities1.Add(entity.PKValue(), entity);
                    includedEntities1.Add(entity.EntityType, entities1);
                }
            }
            Dictionary<EntityType, Dictionary<string, EntityBase>> includedEntities2 =
                new Dictionary<EntityType, Dictionary<string, EntityBase>>();
            foreach (EntityBase entity in group2)
            {
                if (includedEntities2.ContainsKey(entity.EntityType))
                {
                    Dictionary<string, EntityBase> entitis1 = includedEntities2[entity.EntityType];
                    entitis1.Add(entity.PKValue(), entity);
                    includedEntities2[entity.EntityType] = entitis1;
                }
                else
                {
                    Dictionary<string, EntityBase> entities1 = new Dictionary<string, EntityBase>();
                    entities1.Add(entity.PKValue(), entity);
                    includedEntities2.Add(entity.EntityType, entities1);
                }
            }

            foreach(Link link in this._Network.Links)
            {
                EntityType fromType = EntityTypeUtil.GetEntityType(link.FromType);
                EntityType toType = EntityTypeUtil.GetEntityType(link.ToType);
                if(includedEntities1.ContainsKey(fromType) && 
                    includedEntities1[fromType].ContainsKey(link.FromKey))
                {
                    if(includedEntities2.ContainsKey(toType) && 
                        includedEntities2[toType].ContainsKey(link.ToKey))
                    {
                        linksToCut.Add(link);
                    }
                }
            }

            return linksToCut;
        }

        private NetworkCluster InitCluster(
            int clusterID, int parentClusterID, 
            int clusterSizeThreshold,
            List<EntityBase> childEntities)
        {
            NetworkCluster cluster = new NetworkCluster(clusterID, parentClusterID, "");
            if (childEntities != null && childEntities.Count > 0 && childEntities.Count < clusterSizeThreshold)
            {
                cluster.ChildEntities.AddRange(childEntities);
            }
            return cluster;
        }
        #endregion

        #region between centrality 
        public void ClusterNetworkByBetweenCentrality(int clusterSizeThreshold)
        {
            List<NetworkCluster> clusters = new List<NetworkCluster>();
            Dictionary<int, List<EntityBase>> connectedEntities = this._Network.GroupConnectedEntities();
            foreach (int groupID in connectedEntities.Keys)
            {
                List<EntityBase> entities = connectedEntities[groupID];
                int clusterID = clusters.Count + 1;
                NetworkCluster cluster = this.InitCluster(clusterID, 0, clusterSizeThreshold, entities);
                clusters.Add(cluster);
                if (entities.Count > clusterSizeThreshold)
                {
                    
                }
            }

            NetworkCluster.Save(this._Network.NetworkName, clusters);
        }

        private void SplitAtBCNode(List<EntityBase> entities, ref List<NetworkCluster> clusters)
        {
            List<Link> links = Network.GetLinksConnectedToEntities(this._Network.Links, entities);
            
            Graph g = new Graph(entities, links);
            BetweennessCentralityMeasure measure=new BetweennessCentralityMeasure();
            Dictionary<Guid, double> bcMeasures = measure.GetVerticeMeasure(g);
            List<Guid> vids = g.Vertices.Keys.ToList();
            Vertice v = g.Vertices[vids[0]];
            double vMeasure = bcMeasures[v.ID];
            foreach(Guid vID in vids)
            {
                if(bcMeasures[vID]>vMeasure)
                {
                    vMeasure = bcMeasures[vID];
                    v = g.Vertices[vID];
                }
            }
            entities.Remove(v.Tag);
            
        }
        #endregion
    }
}
